# date:20210330
from typing import List

# 时间复杂度：O(mn), 空间复杂度：O(1)
# 时间：36.61%  内存：84.69%
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        for i in range(len(matrix)-1, -1 , -1):
            if target >= matrix[i][0]:
                for j in range(len(matrix[0])):
                    if target == matrix[i][j]:
                        return True
                return False
        return False


# 两次使用二分法，时间复杂度：O(log(mn)), 空间复杂度：O(1)
#
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        pass


matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]]
target = 3
print(Solution().searchMatrix(matrix, target))


matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]]
target = 13
print(Solution().searchMatrix(matrix, target))


matrix = [[1]]
target = 1
print(Solution().searchMatrix(matrix, target))